A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows

This paper presents a new hybrid variable neighborhood-tabu search heuristic for the Vehicle Routing Problem with Multiple Time windows. It also proposes a minimum backward time slack algorithm applicable to a multiple time windows environment. This algorithm records the minimum waiting time and the minimum delay during route generation and adjusts the arrival and departure times backward. The implementation of the proposed heuristic is compared to an ant colony heuristic on benchmark instances involving multiple time windows. Computational results on newly generated instances are provided.     

A note on the time travel approach for handling time windows in vehicle routing problems

In this paper, we identify two cases in which the proposition for calculating time window penalties presented in Nagata, Y., Bräysy, O. and Dullaert, W. A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows, Computers & Operations Research 2010;37(4): 724–37 yields incorrect results. We derive the corrected proposition and use numerical studies to show that a significant proportion of the evaluations performed by a Tabu Search for VRPTW falls under the two incorrect cases. Moreover, we demonstrate that the incorrect time window handling has a significant negative impact on the solution quality of the Tabu Search.     

Statistical analysis of distance-based path relinking for the capacitated vehicle routing problem

In this paper we develop an intelligent path relinking procedure for the capacitated vehicle routing problem, based on the relocate distance. This procedure transforms an incumbent solution into a guiding solution in a minimal number of relocate moves. In each step of the path relinking procedure, one customer is removed from the solution and re-inserted in another position.     

Balancing CapEx reduction and network stability with stable routing–virtual topology capacity adjustment (SR–VTCA)

This paper investigates the merits of the SR–VTCA (stable routing–virtual topology capacity adjustment) approach as a mechanism to find a beneficial trade-off between network stability and reduction in capital expenditures (CapEx). These are two main objectives for the entities that own the optical infrastructure, such as network operators (NOs), and those also acting as Internet service providers (ISPs). The SR–VTCA scheme is a novel approach to adapt transparent optical networks to time-varying traffic by adjusting the number of lightpaths between node pairs, while keeping the IP routing unchanged. Lightpath bundling (LB) and anycast (AS) switching are combined in SR–VTCA operation to advertise lightpath additions/removals to the IP layer as mere adjustments (increments or decrements) in the capacity, allowing to keep the IP routing stable, and thus, simplifying control plane operations. On the contrary, a fully-reconfigurable (FR) network design, where IP routing can be also modified, would increase the burden in the control plane, but at a higher CapEx reduction, since the optical infrastructure is used more efficiently. In this work, we investigate the CapEx overprovision introduced by SR–VTCA with respect to a FR scheme. In order to do this, SR–VTCA planning problem is first modeled as a MILP formulation. A heuristic procedure based on traffic domination is then proposed to solve large instances of the problem. Exhaustive experiments are conducted comparing the SR–VTCA solutions obtained by the aforementioned MILP and heuristic proposal with solutions found by other optimization methods presented in the literature to solve the FR planning problem. Finally, the results show that SR–VTCA can achieve similar results to the FR case in terms of CapEx reduction, while a huge number of IP reroutings are saved by maintaining IP stability. Thus, SR–VTCA provides an advantageous balance between CapEx overprovisioning and the control plane overhead associated with IP rerouting.     

A construction and improvement heuristic for a liquefied natural gas inventory routing problem

We present a large scale ship routing and inventory management problem for a producer and distributor of liquefied natural gas (LNG). The problem contains multiple products, inventory and berth capacity at the loading port and a heterogeneous fleet of ships. The goal is to create an annual delivery program to fulfill the producer’s long-term contracts at minimum cost, while maximizing the revenue from selling LNG in the spot market. To solve this problem we have developed a construction and improvement heuristic (CIH).The CIH is a multi-start local search heuristic that constructs a set of solutions using a greedy insertion procedure. The solutions are then improved using either a first-descent neighborhood search, branch-and-bound on a mathematical formulation, or both. Tests on real-life instances show that the CIH provides good solutions in a short amount of time.     

Providing reliable and link stability‐based geocasting model in underwater environment

This paper presents a geocast technique for underwater sensor networks. The model named as Routing and Multicast Tree based Geocasting (RMTG) (TRACE'10, Bhopal, India, 2010; ICWET'10, Mumbai, India, 2010) has been designed for underwater sensor networks. In our previous work (TRACE'10, Bhopal, India, 2010; ICWET'10, Mumbai, India, 2010) we proposed only a theoretical model for underwater geocasting. The RMTG technique uses greedy forwarding and previous hop handshaking to route the packets towards the geocast region and further disseminates the data within the geocast region by creating a multicast shortest path tree. We also presented various link broken scenarios along with their solutions. The proposed model does not use the flooding technique to deliver the packets inside the geocast region that is used in most of the geocasting techniques. In this paper, we present the simulated RMTG model. The simulation results show that the proposed model provides an efficient distribution of data in the geocast region in terms of node mobility handling, packet delivery ratio and a better end‐to‐end latency. Most of the work on geocasting has been done for mobile and vehicular ad hoc networks; hence we present in this paper a novel simulated model for underwater environment. Copyright © 2011 John Wiley & Sons, Ltd.     

A bi-level school bus routing problem with bus stops selection and possibility of demand outsourcing

This paper develops a bi-level mathematical model for the school bus routing problem aiming at designing an efficient transportation system considering the possibility of predicting the students’ response. In the real world, the demand for using private cars depends on how well public transportation systems are operating especially in metropolitan cities. An inefficient public transportation will lead to an increase in the demand for using private cars. This issue will result in problems such as increased traffics and urban pollutions. To address this issue, an efficient public transportation system is designed by developing a new bi-level mathematical model. In the proposed model, the designer of the public transportation system, as the upper-level decision-maker, will locate appropriate bus stops and identify bus navigation routes. Subsequently, the decision regarding the allocation of students to transportation systems or outsourcing them will be made at the lower level which is considered as an operational-level decision-making. To solve this problem, two hybrid metaheuristic approaches named GA-EX-TS and SA-EX-TS have been proposed based on location-allocation-routing (LAR) strategy. The performance of these proposed methods is compared with exact solutions achieved from an explicit enumeration approach followed in the small-scale instances. Finally, the proposed approaches are used to solve 50 random instance problems. Comparing the results of the two tuned hybrid algorithms and conducting the sensitivity analysis of the model provide evidence for the good performance of the proposed approach.     

A heuristic algorithm for a single vehicle static bike sharing rebalancing problem

The static bike rebalancing problem (SBRP) concerns the task of repositioning bikes among stations in self-service bike-sharing systems. This problem can be seen as a variant of the one-commodity pickup and delivery vehicle routing problem, where multiple visits are allowed to be performed at each station, i.e., the demand of a station is allowed to be split. Moreover, a vehicle may temporarily drop its load at a station, leaving it in excess or, alternatively, collect more bikes from a station (even all of them), thus leaving it in default. Both cases require further visits in order to meet the actual demands of such station. This paper deals with a particular case of the SBRP, in which only a single vehicle is available and the objective is to find a least-cost route that meets the demand of all stations and does not violate the minimum (zero) and maximum (vehicle capacity) load limits along the tour. Therefore, the number of bikes to be collected or delivered at each station must be appropriately determined in order to respect such constraints. We propose an iterated local search (ILS) based heuristic to solve the problem. The ILS algorithm was tested on 980 benchmark instances from the literature and the results obtained are competitive when compared to other existing methods. Moreover, our heuristic was capable of finding most of the known optimal solutions and also of improving the results on a number of open instances.     

Home health care routing and scheduling: A review

In home health care (HHC) operations, nurses are scheduled and routed to perform various services at clients' homes. As this often requires a combination of vehicle routing and scheduling approaches, resulting optimization problems are complex and, hence, of high interest to stakeholders such as researchers, practitioners and policy-makers. With demand for HHC expected to increase substantially, future work is essential to decrease costs and to guarantee service quality. In this review, we provide a comprehensive overview of current work in the field of HHC routing and scheduling with a focus on considered problem settings. Recent advances in HHC optimization are highlighted and future research directions discussed.     

New dynamic metric indices for secondary memory

Metric indices support efficient similarity searches in metric spaces. This problem is central to many applications, including multimedia databases and repositories handling complex objects. Most metric indices are designed for main memory, and also most of them are static, that is, do not support insertions and deletions of objects. In this paper we introduce new metric indices for secondary memory that support updates, that is, they are dynamic. First, we show how the dynamic and memory-based Dynamic Spatial Approximation Tree (DSAT) can be extended to operate on secondary memory. Second, we design a dynamic and secondary-memory-based version of the static List of Clusters (LC), which performs well on high-dimensional spaces. The new structure is called Dynamic LC (DLC). Finally, we combine the DLC with the in-memory version of DSAT to create a third structure, Dynamic Set of Clusters (DSC), which improves upon the other two in various cases. We compare the new structures with the state of the art, showing that they are competitive and outstand in several scenarios, especially on spaces of medium and high dimensionality.